/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 030.c
 * Prime Number
 ***********************************************************************************************/

#include <stdio.h>
#include <math.h>
#include <string.h>

/*
 *
 */

#define MAX 1000000
#define SWITCH 1 
int p[MAX];

// Prime Number varification with table
int isPrime(int n)
{
    if (n < 2)
        return(0);
    else if (n == 2)
        return(1);
    else if (!(n%2))
        return(0);
    int i = 0;
    int cut_off = sqrt(n);
    for (i = 0; p[i] != 0 && p[i] <= cut_off; i++)
    if (n % p[i] == 0) return(0);
    return(1);
}

int main()
{

#if SWITCH == 0
    // Prime Number varification with table
    memset(p, 0, MAX*sizeof(int));
    int i = 0, curr = 0;
    for (i = 1; i <= MAX; i++)
        // if (i != 2 && i%2 == 0) continue;
        // this test is included in isPrime test
        if (isPrime(i))
        {
            p[curr++] = i;
            //printf((curr % 15) ? "%4d" : "%4d\n", i);
        }
    printf("Total %d prime numbers\n", curr);

#elif SWITCH == 1
    //too slow when MAX grows up
    int i = 0, flag = 0, j = 0, count = 0;
    for (i = 3; i<= MAX; i += 2)
    {
        for (flag = 1, j = 3; flag && j < i/2; j += 2)
            if (!(i%j)) flag = 0;
        if (flag) count++; // printf(++count%15 ? "%4d" : "%4d\n", i);
    }
    printf("Total %d prime numbers\n", count);
#endif
}

